#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void minChange(int A[], int size, int  n)
{
    vector<int> c(n+1, 1000000);
    vector<int> s(n+1, 0);
    
    c[0] = 0; 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < size; j++) {
	    if (A[j] <= i && 1 + c[i-A[j]] < c[i]) {
		c[i] =  1 + c[i-A[j]];
                s[i] = j;
	    }
	}
    }
    cout << "Minimum coins for " << n << "is " << c[n] << endl;
    int cur = n;
    int sum = n;
    getchar();
    while(cur > 0) {
        cout << A[s[cur]] << " " ;
        cur = cur - A[s[cur]];
    }
    cout << endl;
}

int ways(int A[], int size, int n)
{
    vector<vector<int> > dp(1+n, vector<int>(size, 0));
    for (int i = 0; i < size; i++) {
        dp[0][i] = 1;
    }
   
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < size; j++) {
            dp[i][j] += (i >= A[j] ? dp[i-A[j]][j] : 0) + (j >= 1 ? dp[i][j-1] : 0);
	}
    }

    for (int i = 0; i <=n; i++) {
        for (int j = 0; j < size; j++)
            cout << dp[i][j] << " ";
	cout << endl;
    } 
    return dp[n][size-1];
}

int main(int argc, char **argv)
{
    int A[] = {1,3,5,20};
   // minChange(A, sizeof(A)/sizeof(int), 35);
    cout << ways(A, sizeof(A)/sizeof(int), 35) << endl;
   /* cout << ways(A, sizeof(A), 10) << endl;
    cout << ways(A, sizeof(A), 35) << endl; */
}
